package fun.coding.search;

public class BinarySearchImpl implements BinarySearch {

    /**
     * Find minimum number from a given shifted array
     * e.g., {2, 3, 4, 5, 1} would return 1.
     * My implementation below is too hard to understand and not straightforward. 
     * @param a
     * @param left
     * @param right
     * @return minimum int for this given array.
     */
    @Override
    public int findMinimumShiftedArray(int[] a, int left, int right) {
        if(left == right) {
            return a[left];
        }
        
        int mid = left + (right - left) / 2; // avoid overflow
        
        // turning point is on the right side.
        if(a[mid] > a[right]) {
            if((right - left) == 1) {
                return a[right];
            } else {
                return findMinimumShiftedArray(a, mid, right);
            }
        } else if(a[mid] < a[left]) { // turning point is on the left side.
            if((right - left) == 1) {
                return a[right];
            } else {
                return findMinimumShiftedArray(a, left, mid);
            }
        } else { // current range is an ascending, so minimum is always on the left.  
            if((right - left) == 1) {
                return a[left];
            } else {
                return findMinimumShiftedArray(a, left, mid);
            }
        }

    }

    /*
     * A much better method than findMinimumShiftedArray
     * e.g., {2, 3, 4, 5, 1} would return 1.
     * TODO: this is WRONG!!
     * 
     * Failed Microsoft on this one. Windoes Azure group questions,
     * how many times an array has been shifted. 
     * 0, 0, 0, 0, 0, 0, 0, return 0
     * 0, 0, 1, 1, 2, 5, 7 return 0
     * 7, 0, 0, 1, 1, 2, 5 return 1
     * 5, 7, 0, 0, 1, 1, 2, return 2 
     * stuck on recursion, clean code.
     * 
     */
    @Override
    public int binarySearchShiftedMin(int[] a, int left, int right) {
        
        if(left >= right) {
            return a[left];
        }
        int mid = left + (right - left) / 2;
        
        if(a[mid] > a[left]) {
            return binarySearchShiftedMin(a, mid + 1, right);
        } else {
            return binarySearchShiftedMin(a, left, mid);
        }
        
    }

    
    /* This should be the most basic binary search, if n does not exist in array, return -1.
     * Return the index of that number
     * If there are duplicate, it will return the first one it encounters. 
     * (non-Javadoc)
     * @see interview.coding.search.BinarySearch#binarySearch(int[], int)
     */
    @Override
    public int binarySearch(int[] array, int n, int left, int right) {
        int mid = left + (right - left) / 2;
        
        if(left > right) {
            return -1;
        }
        
        if(n > array[mid]) {
            return binarySearch(array, n, mid + 1, right);
        } else if(n < array[mid]) {
            return binarySearch(array, n, left, mid - 1);
        } else {
            return mid; 
        }
        
    }

    /*
     * Find the index of the first appearance in a binary array
     * {2, 5, 5, 5, 7, 9} for n =5, return 1.
     * */
    @Override
    public int binarySearchFirstAppearance(int[] array, int n, int left,
            int right) {
        int mid = left + (right - left) / 2;
        
        if(left > right) {
            return -1;
        }
        
        if(left == right) {
            return left;
        }
        
        if(n > array[mid]) {
            return binarySearchFirstAppearance(array, n, mid + 1, right);
        } else if(n < array[mid]) {
            return binarySearchFirstAppearance(array, n, left, mid - 1);
        } else {
            // Basically it will keep doing the binary search on the left part. 
            return binarySearchFirstAppearance(array, n, left, mid);
        }
        
    }

    private int binarySearchLastAppearance(int[] array, int n, int left, int right) {
        if(left > right)
            return -1;
        
        if(left == right)
            return left;
        
        int mid = left + (right - left) / 2;
        if(n > array[mid]) {
            return binarySearchLastAppearance(array, n, mid + 1, right);
        } else if(n < array[mid]) {
            return binarySearchLastAppearance(array, n, left, mid - 1);
        } else {
            // keep searching on the right part. 
            return binarySearchLastAppearance(array, n, mid, right);
        }
        
    }
    
    /*
     * 6, 7, 2, 3, 4, 5 
     * The catch here is if the number we are looking for is within the ordered part, then it is normal binary search. 
     * Or else, we still need to figure out which part it is on. 
     */
    @Override
    public int binarySearchShifted(int[] array, int n, int left, int right) {
        if(left > right) {
            return -1;
        }
        
        int mid = left + (right - left) / 2;
        
        if(array[mid] == n) {
            return mid;
        }
        
        // right part is sorted
        if(array[mid] <= array[right]) {
            if(n > array[mid] && n <= array[right]) {
                return binarySearch(array, n, mid + 1, right);
            } else {
                return binarySearchShifted(array, n, left, mid - 1);
            }
            
        } else { // left part is sorted
            if(n < array[mid] && n >= array[left]) {
                return binarySearch(array, n, left, mid - 1);
            } else {
                return binarySearchShifted(array, n, mid + 1, right);
            }
        }
        
    }

    /* Find the number of occurance of one number in a sorted array.
     * {2, 5, 5, 5, 7, 9}  n = 5 return 3 
     * Should first use binary search to search for that number, then keep binary search to the left and then to the right. 
     * */
    @Override
    public int countOccurance(int[] array, int number) {
        return binarySearchLastAppearance(array, number, 0, array.length - 1) - binarySearchFirstAppearance(array, number, 0, array.length - 1) + 1;
    }


    
}
